
//*************快排**************
//	-2018-3-10
#include<vector>
/*-----------------功能函数--------------------------*/

void show_data(vector<int> data){
	cout << endl;
	for each (auto iter in data){
		cout << iter << " ";
	}
	/*linux下更改为
	for (auto iter : data){
		cout<<iter<<" ";
	}
	*/
}
template<typename T>
void bi_swap(T& A,T& B){
	static T C = 0;
	C = A;
	A = B;
	B = C;
}
/*检查数据的大小排列
		默认为由小到大
		返回值：不和趋势的元素数
	大约：25s：50万int数的排序
*/
int check_data(vector<int> data,bool small2big=true){
	long count=0;
	long end=data.size();
	assert(end>=2);
	if(small2big){
		for(long i=1;i<end;i++){
			count+=(data[i-1] <= data[i] ? 0 : 1 );
		}
	}
	else{
		for(long i=1;i<end;i++){
			count+=(data[i-1] >= data[i] ? 0 : 1 );
		}
	}
	cout<<"不和大小趋势的元素有："<<count<<endl;
	
	return count;
}
/**********百科官方版1**************************/
template<typename T>
void quick_sort_recursive(vector<T>& arr, int start, int end) {
	if (start >= end)
		return;
	T mid = arr[end];
	int left = start, right = end - 1;
	while (left < right) {
		while (arr[left] < mid && left < right)
			left++;
		while (arr[right] >= mid && left < right)
			right--;
		std::swap(arr[left], arr[right]);
	}
	if (arr[left] >= arr[end])
		std::swap(arr[left], arr[end]);
	else
		left++;
	quick_sort_recursive(arr, start, left - 1);
	quick_sort_recursive(arr, left + 1, end);
}

template<typename T> 
void quick_sort(vector<T>& arr,int len) {

	quick_sort_recursive(arr, 0, len);
}


/****************开发过程版**************************/

//每一步都要搞清楚，想不出来就写流程
//分析出所有的递归过程中的情况，并用代码覆盖
//
int flat(vector<int>& data, int start, int end){
	//[1]get a number: 1\first data.	2\random data
	int wait2compare = start;
	//cout << endl << wait2compare;
	start += 1;
	while (end > start ){
		//[2]compare start,end;
		if ((data[start]>data[wait2compare]) && (data[end]<data[wait2compare])){
			bi_swap<int>(data[start], data[end]);
			start++;
			end--;
		}
		if (data[start] <= data[wait2compare]){
			start += 1;
		}
		if (data[end] >= data[wait2compare]){
			end -= 1;
		}
	}
	//[3]change the two value
	data[wait2compare]>data[end] ? bi_swap<int>(data[wait2compare], data[end]):0;
	return end;
}
void quick_sort1(vector<int>& data,int start,int end){
	//递归操作首先调试完成非递归部分
	if(end>start){ 
		//cout << endl << "参数：" << start << "-" << end;
		int middle = flat(data, start, end);
		//show_data(data);
		cout << "middle" << middle;
		quick_sort1(data, start, middle-1);
		quick_sort1(data, middle, end);   //为什么不减1?
	}
}

/****************无注释·泛型版**********************/
template<typename T>
int flat1(vector<T>& data, int start, int end){
	int tmp = start++;
	while (end > start){
		if ((data[start]>data[tmp]) && (data[end]<data[tmp]))	bi_swap<T>(data[start++], data[end--]);
		if (data[start] <= data[tmp])	start++;
		if (data[end] >= data[tmp])		end--;
	}
	data[tmp]>data[end] ? bi_swap<int>(data[tmp], data[end]) : void(0);  //更为严格的类型检查
	return end;
}
template<typename T>
void quick_sort2(vector<T>& data, int start, int end){
	if (end>start){
		int middle = flat1(data, start, end);
		quick_sort2(data, start, middle - 1);
		quick_sort2(data, middle, end);  
	}
}
/***************************************************/
void test1(){
	vector<int> data;
	int end = 200;
	for (int i = 0; i < end; i++){
		data.push_back(rand()%100);
	}
	show_data(data);
	quick_sort2<int>(data,0,data.size()-1);
	show_data(data);
}
